It will be recalled that so-called “channel” encoding consists, when the “code words” sent to the receiver are formed, of introducing a certain amount of redundancy in the data to be transmitted. More particularly, by means of each code word, a predetermined number k of information symbols are transmitted which are chosen from a predetermined “alphabet” of finite size q; to these k information symbols are added a number (n−k) of so-called “parity” symbols, taken from the same alphabet, so as to form code words c=(c1,c2, . . . ,cn) of length n; the set of the rules for calculation of the parity symbols as a function of the information symbols defines a “code”, or “encoding method”, of “dimension” k and “length” n, thus characterized by a certain number of code words constituting a sort of dictionary. A code may be conveniently defined by means of a matrix H, of size (n−k)×n, termed “parity matrix”: a word c of given length n is a code word if, and only if, it satisfies the relationship: H·cT=0 (where the exponent T indicates the transposition).
At the receiver, the associated decoding method then judiciously uses this redundancy to detect any transmission errors and if possible to correct them. There is a transmission error if the difference e between a received word r and the corresponding code word c sent by the transmitter is non-zero.
More particularly, the decoding is carried out in two main steps.
The first step consists of associating an “associated code word” with the received word. To do this, the decoder first of all calculates the “error syndrome” s=H·rT=H·eT. If the syndrome is zero, it is assumed that no transmission error has occurred, and the “associated code word” will then simply be taken to be equal to the received word. If that is not the case, it is thereby deduced that some symbols in the received word are erroneous, and a correction algorithm is then implemented which is adapted to estimate the value of the error e; the algorithm will thus provide an estimated value ê such that (r-ê) is a code word, which will then constitute the “associated code word”.
The second step simply consists in reversing the encoding method, that is to say in removing the redundant symbols from the “associated code word” to retrieve the initial information symbols.
More particularly, the invention concerns the first of these two steps, and the conditions for implementation of the correction algorithm.
The purpose of a correction algorithm is to associate with the received word the code word situated at the shortest Hamming distance from this received word, the “Hamming distance” being, by definition, the number of places where two words of the same length have a different symbol. Each code thus provides an error correction capacity which is limited by the shortest Hamming distance between any two code words, which is termed the “minimum distance” of the code d; more particularly, when the chosen correction algorithm is used to find the position of possible errors in any received word, and to provide a replacement symbol for each of these positions, one can be sure of being able to optimally correct INT[(d−1)/2] errors for a code of minimum distance d (“INT” designates the integer part). If the received word contains a number of errors strictly greater than INT[(d−1)/2], the algorithm will in certain cases capable of proposing a correction, but it will then of course be very doubtful that such a correction will be right, that is to say that the associated code word really is the code word sent by the transmitter.
The capability of a correction algorithm to propose a correction of a received word is faithfully represented by the formula:2t≦Δ,where t is the number of erroneous symbols in the received word, and Δ is a strictly positive integer which we will call the “solving capability” of the algorithm. If the value of (2t) is less than or equal to the solving capability, the correction algorithm will be capable of correcting the received word. If the value of (2t) is greater than the solving capability, the algorithm can:
either simply fail in its correction attempt,
or be capable of proposing a correction of the received word; in this case, if that correction is accepted, the risk is taken of it being erroneous, i.e. that the code word proposed is not in fact the word sent; clearly, the greater (2t) is with respect to Δ, the higher the risk.
Taking into account the above considerations concerning the minimum distance d of the code, the algorithm considered will be said to be “maximum” ifΔ=d−1,and “sub-maximum” ifΔ<d−1.
Among known encoding methods, “Reed-Solomon” codes may be cited, which are reputed for their efficiency. These codes, however, have the particularity that the length n of the code words is necessarily less than or equal to the size q of the alphabet of the symbols. On account of this, if a Reed-Solomon code is desired having code words of great length, high values of q must be envisaged, which leads to costly implementations in terms of calculation and storage in memory. Moreover, high values of q are sometimes ill-adapted to the technical application envisaged.
However, for modern information carriers, for example in recordings on CD (“compact discs”) and DVD (“digital video discs”), it is sought to increase the density of information. When such a carrier is affected by a physical defect such as a scratch, a high number of information symbols may be rendered unreadable. This problem may nevertheless be remedied using very long code words. For this reason, it has been sought to build codes which naturally provide words of greater length than Reed-Solomon codes.
In particular so-called “algebraic geometric codes” or “Goppa geometric codes” have recently been proposed (see for example “Algebraic Geometric Codes” by par J. H. van Lint, in “Coding Theory and Design Theory” 1st part, IMA Volumes Math. Appl., volume 21, Springer-Verlag, Berlin, 1990). These codes are constructed from algebraic curves defined on the basis of an alphabet of q elements structured into a Galois field. An important parameter of such a curve is its “genus” g. In the particular case where the curve is a simple straight line (the genus g is then zero), the algebraic geometric code reduces to a Reed-Solomon code. In certain cases, algebraic geometric codes make it possible to achieve a length equal to (q+2g√{square root over (q)}), which may be very high; for example, with an alphabet length of 256 and a genus equal to 120, code words are obtained of length 4096.
Algebraic geometric codes are, as has been said, advantageous as to the length of the code words, but they have the drawback of requiring (on the basis of current knowledge at least) decoding algorithms that are rather complex, and thus rather expensive in terms of equipment (software and/or hardware) and processing time. This complexity is in fact greater or lesser according to the algorithm considered, a greater complexity being in principle the price to pay for increasing the error correction capacity of the decoder. (see for example the article by Tom Høholdt and Ruud Pellikaan entitled “On the Decoding of Algebraic-Geometric Codes”, IEEE Trans. Inform. Theory, vol. 41 no. 6, pages 1589 to 1614, November 1995).
It should be noted that for these algorithms, only a lower bound of their solving capability Δ is available, except in the “trivial” case of the maximum algorithm for correction of Reed-Solomon codes (called the “Berlekamp-Massey algorithm”), for which the solving capability is precisely known and is equal to Δ=n−k. A generalization of this algorithm to non-zero algebraic geometric codes, termed “basic” algorithm, has been proposed by A. N. Skorobogatov and S. G. Vladut, in the article entitled “On the Decoding of Algebraic-Geometric codes”, IEEE Trans. Inform. Theory, vol. 36 no. 5, pages 1051 to 1060, November 1990), this algorithm provides a solving capability at least equal to Δ=n−k−2g.
However, the minimum distance d for a algebraic geometric code is at least equal to (n−k+1−g). It is thus clear that the basic algorithm is “sub-maximum”, and this is all the more so the greater the genus g of the algebraic curve. With the aim of improving the solving capability, Skorobogatov and Vladut proposed, in the same article cited above, a “modified” version of the “basic” algorithm. This “modified” algorithm has a solving capability at least equal to Δ=n−k−g−s, where s is a parameter dependent on the algebraic curve chosen, which may furthermore sometimes be zero (this is the case for example for so-called “hyperelliptic” algebraic curves.
The basic algorithm proceeds essentially in three steps:    1) constructing a “syndromes matrix” S, of size (n−k)×(n−k), of which each coefficient Sij, where j is less than or equal to a “boundary” value w(i), is equal to a linear combination judiciously chosen of the elements sv (v=1,2, . . . , n−k) of the syndrome s, the coefficients Sij beyond the boundary remaining indeterminate,    2) identifying the position of the errors in the received word, by solving a certain number of linear equations of which the coefficients are taken from the syndromes matrix S, and    3) correcting the erroneous symbols of the received word of which the position is now known.
The modification introduced by the modified basic algorithm consists in a new mode of operation for the second step of the algorithm. More particularly, for any integer μ between 1 and (n−k), the following system of linear equations is considered:
                                                        ∑                              i                =                1                            μ                        ⁢                                                  ⁢                                          l                                                                                          ⁢                  i                                            ⁢                              S                                  i                  ⁢                                                                          ⁢                  j                                                              =          0                ,                              for            ⁢                                                  ⁢            j                    =          1                ,        2        ,                                  ⁢        …        ⁢                                  ,                  w          ⁡                      (            μ            )                          ,                            (        1        )            where the values of the unknowns li are to be found in the same alphabet of symbols as the elements of the code words. An integer λ0 is then sought which is the smallest value of μ for which such a system has a non-trivial solution, that is to say a solution where the coefficients li are not all zero.
Skorobogatov and Vladut thus teach to consider successively and independently the sub-matrices of S size μ×w(μ), first for μ equal to 1, then for μ equal to 2, and so forth until one is found for which the lines are linearly dependent.
However, a question which is important from a practical point of view and which must be posed in relation to any calculation algorithm, is that of its complexity, that is to say the number of arithmetical operations which it requires. It can be shown that the solution of the modified basic algorithm, as succinctly described above, requires of the order of n4 arithmetical operations (in the symbols alphabet), where n is, it should be recalled, the length of the codewords. However, the complexity of the basic algorithm is only of the order of n3. In this manner the increase in the solving capability according to this approach is thus made at the cost of an increase in complexity.